package code.commonAlgorithm;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

/**
 * @author 26029
 * @date 2025/4/22
 * @description
 */
public class Calculator {
    // 实现基本计算器：输入为 -> 0-9、()、+-*/
    public int calculate(String s) {
        // s去空格
        s = s.replace(" ", "");
        // 负号前填0
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '-' && (i == 0 || s.charAt(i - 1) == '('))
                sb.append('0');
            sb.append(c);
        }
        s = sb.toString();
        // 定义优先级
        Map<Character, Integer> map = new HashMap<>();
        map.put('+', 1);
        map.put('-', 1);
        map.put('*', 2);
        map.put('/', 2);
        // 双栈
        Deque<Integer> numStack = new ArrayDeque<>();
        Deque<Character> opStack = new ArrayDeque<>();
        // 循环遍历
        int len = s.length();
        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            // 是数字
            if (Character.isDigit(c)) {
                int pos = i + 1;
                int num = c - '0';
                while (pos < len && Character.isDigit(s.charAt(pos))) {
                    num = 10 * num + (s.charAt(pos) - '0');
                    pos++;
                }
                i = pos - 1;
                numStack.push(num);
            }
            // 是左括号
            else if (c == '(') {
                opStack.push('(');
            }
            // 是右括号
            else if (c == ')') {
                while (!opStack.isEmpty() && opStack.peek() != '(') {
                    cal(numStack, opStack);
                }
                opStack.pop();
            }
            // 是操作符
            else {
                // 如果新的操作符比栈顶的优先级高，则不计算栈顶
                while (!opStack.isEmpty() && opStack.peek() != '(' && map.get(c) <= map.get(opStack.peek())) {
                    cal(numStack, opStack);
                }
                opStack.push(c);
            }
        }
        while (!opStack.isEmpty())
            cal(numStack, opStack);
        return numStack.peek();
    }

    private void cal(Deque<Integer> numStack, Deque<Character> opStack) {
        int a1 = numStack.pop();
        int a2 = numStack.pop();
        char op = opStack.pop();
        switch (op) {
            case '+' -> numStack.push(a2 + a1);
            case '-' -> numStack.push(a2 - a1);
            case '*' -> numStack.push(a2 * a1);
            case '/' -> numStack.push(a2 / a1);
        }
    }

    public static void main(String[] args) {
        Calculator c = new Calculator();
        System.out.println(c.calculate("1*2-3/4+5*6-7*8+9/10"));
    }
}
